﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Sets;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Parsing 
{
    public class NFA<TState> : IParser
    {
        private readonly Func<ISet<TState>, IMap<TState, bool>> _createMap;
        private readonly ISet<TState> _Q;
        private readonly TState _q0;
        private readonly IMap<TState, IList<Tuple<TState, char>>> _predecessors;
        private readonly ISet<TState> _F;

        public NFA(ISet<TState> Q, TState q0, IMap<TState,IList<Tuple<TState,char>>> predecessors, ISet<TState> F, 
                   Func<ISet<TState>, IMap<TState,bool>> createMap = null)
        {
            _Q = Q;
            _q0 = q0;
            _predecessors = predecessors;
            _F = F;
            _createMap = createMap ?? (set => AlgoritmiaFactory.Maps<TState, bool>.Default);
        }

        #region IParser implementation

        public bool Accepts(string s)
        {
            var P = new IMap<TState, bool>[s.Length + 1];
            for(int i = 0; i <= s.Length; i++)
            {
                P[i] = _createMap(_Q);
            }
            foreach(var q in _Q)
            {
                P[0][q] = false;
            }
            P[0][_q0] = true;
            for(int i =1 ; i <= s.Length; i++)
            {
                foreach(var q in _Q)
                {
                    P[i][q] = _predecessors[q].Any(tp => P[i - 1][tp.Item1] && tp.Item2 == s[i - 1]);
                }
            }
            return _F.Select(f => P[s.Length][f]).Any(e => e);
        }

        #endregion
    }
}
